package com.aerospace.treenode;

import com.sun.jmx.remote.internal.ArrayQueue;

import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class TreeBS {
    static class TreeNode{
        int value;
        TreeNode left;
        TreeNode right;
        public TreeNode(int value){
            this.value= value;
        }
    }
    TreeNode root;
    public TreeBS(int[] array){
        root= makeBinaryTreeByArray(array,1);
    }

    /**
     * 采用递归方式创建一棵二叉树
     * @param array
     * @param index
     * @return
     */
    private static TreeNode makeBinaryTreeByArray(int[] array, int index) {
        if (index<array.length){
            int value = array[index];
            if (value!=0){
                TreeNode t = new TreeNode(value);
                array[index]=0;
                t.left=makeBinaryTreeByArray(array,index*2);
                t.right=makeBinaryTreeByArray(array, index*2+1);
                return t;
            }
        }
        return null;
    }

    /**
     * 深度优先遍历，相当于先根遍历
     * 采用非递归实现
     * 需要辅助数据结构：栈
     */
    public void depthOrderTraversal(){
        if (root==null){
            System.out.println("empty tree");
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(stack.isEmpty()==false){
            TreeNode node = stack.pop();
            System.out.println(node.value + "  ");
            if (node.right!=null) stack.push(node.right);
            if (node.left!=null) stack.push(node.left);
        }
        System.out.println("\n");
    }

    /**
     * 广度优先遍历
     * 采用非递归实现
     * 需要辅助数据结构：队列
     */
    public void levelOrderTraversal(){
        if (root==null){
            System.out.println("empty tree");
            return;
        }
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        Queue<TreeNode> q = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            System.out.println(node.value+"");
            if (node.left!=null) queue.add(node.left);
            if (node.right!=null) queue.add(node.right);
        }
        System.out.println("\n");
    }

    public static void main(String[] args) {
        int[] arr={0,13};
        TreeBS treeBS = new TreeBS(arr);
        treeBS.depthOrderTraversal();
        treeBS.levelOrderTraversal();
    }
}
